package likou.bingchaji;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/30 11:33
 */
public class _778 {
    private int N;
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    class DJS {
        DJS p;

        DJS() {
            this.p = this;
        }

        DJS find() {
            if (p.p != p) {
                p = p.find();
            }
            return p;
        }

        void union(DJS b) {
            this.find().p = b;
        }
    }

    public int swimInWater(int[][] grid) {
        N = grid.length;
        int[] parent = new int[N * N];
        DJS[] union = new DJS[N * N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                parent[grid[i][j]] = getIndex(i, j);
            }
        }

        for (int i = 0; i < parent.length; i++) {
            DJS d = new DJS();
            int x = parent[i] % N;
            int y = parent[i] / N;
            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                if (inArea(newX, newY) && grid[newX][newY] <= i) {
                    d.union(union[getIndex(newX, newY)]);
                    union[parent[i]] = d;
                }
                if (union[0].find() == union[N * N - 1].find()) {
                    return i;
                }
            }
        }
        return -1;
    }

    private int getIndex(int i, int j) {
        return i * N + j;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}
